1. Field of the Invention
This invention relates to methods of and apparatus for partitioning an array of items, and more particularly to partitioning an array of n items into p subarrays so that a maximum weight of the array elements within any subarray is minimized.
2. Background of Related Art
Array partitioning problems arise in a number of load balancing, scheduling, data layout, video compression and image processing settings. Although the present invention relates generally to the partitioning of multiple dimension arrays, for simplicity of description partitioning will be described herein with respect to two dimensions only, with the understanding of the applicability to arrays of higher dimensions.
The problem of partitioning a set of items into roughly equal weight subsets is a fundamental one. Consider partitioning an n.times.n array of items into rows and columns having a number p of intervals there between in both dimensions. The p intervals in both dimensions can be understood as forming blocks of array elements. The present invention relates to and improves upon methods and apparatus for determining those partitions p which minimize a maximum weight given to the array elements in each of the resulting blocks. The `weight` in this determination may be virtually any characteristic of the array elements particular to the application for which the invention is being utilized. For instance, for purposes of description only, the `weight` of determined blocks in an n.times.n array will be defined as the sum of the array elements contained within the partitioned blocks.
The definition of the `weight` associated with the partitioned blocks in an array, the type of partitions allowed, and the dimensions of the partitioned arrays depends upon the particular application at hand. Particular applications having n.times.n arrays with weighting based on the sum of the elements contained within the partitioned blocks include load balancing for parallel processing, data partitioning for parallel software, and compilers for high-performance parallel languages. Moreover, partitioning of n.times.n arrays is particularly applicable for use in the compression of the data required to represent a video signal. Some video compression techniques take advantage of the fact that typically only portions of a video image change from frame to frame based on the motion of an object. In this application, the present invention applies to the determination of motion estimation by matching partitioned blocks between frames of a video image. Here, it is typically desired that given a maximum desired weight .delta. of any partitioned block, that the partitions be minimized such that the maximum weight of any partitioned block is at most the desired weight value .delta..
The present invention will generally be described with respect to the solution of two types of partitioning:
(a) Given a desired number of partitioned blocks B, partition a given array into at most B blocks having the weight of any partitioned block B minimized; and PA1 (b) Given a desired maximum weight .delta., partition a given array into a minimum number of blocks B such that the weight of any block B in the partition is no greater than the desired maximum weight .delta..
There is a need for equipment such as that implementing parallel processing or image compression to partition multidimensional arrays of data with improved speed, efficiency and accuracy.
Conventional partitioning techniques are extended to two dimensions, e.g., when given a desired number of partitions p, the effort is to find the p.times.p partitions that minimize the maximum of the weight functions of the individual blocks. This is known as the "two dimensional p.times.p partition problem". In a related situation extended into the two dimensional case, given a desired maximum value for the weight function .delta., find the minimum number of partitions p for which there exists p.times.p partitions forming blocks each having a weight function no greater than the desired maximum weight .delta.. This is known generally as the "two dimensional .delta.-weight partition problem."
Consider AA to be an n.times.n array. The effort is to divide each column (e.g., AA[1, n]) into p intervals defined by horizontal dividers (h.sub.0 =0)&lt;h.sub.1.ltoreq.h.sub.2.ltoreq.. . . .ltoreq.h.sub.p-1.ltoreq.(h.sub.p =n), and each row (e.g., AA[1,n]) into p other intervals defined by the vertical dividers (v.sub.0 =0)&lt;v.sub.1.ltoreq.v.sub.2.ltoreq.. . . .ltoreq.v.sub.p-1.ltoreq.(v.sub.p =n). This partitioning defines p.sup.2 blocks given by AA[h.sub.i-1 +1 . . . h.sub.i, v.sub.j-1 +1 . . . v.sub.j ] for each i, j.
Two weight functions arise commonly in practice: the additive weight function: EQU F(A[i,j])=.SIGMA..sub.k=i.sup.k=j A[k]
and the Hamming weight function H.sub.c for a given parameter c, relative to another array B of size n, given by: EQU H.sub.c (A[i,j])=min.sub.-c.ltoreq.k.ltoreq.c H(B[i+k,j+k],A[i,j])
where H(X,Y) gives the Hamming distance between two segments X and Y of identical length.
Using either of these or another weight function, the resultant maximum of the weight values is determined by: EQU maxi.sub.i=1.sup.i=p f(A[d.sub.i-1 +1 . . . d.sub.i ])
Conventional weight functions for the partitioned blocks are the additive weight function F or the Hamming weight function H.sub.c.
The minimum of the maximum weights of the individual blocks in a partition (MAX norm) is given by: EQU max.sub.i=1,j=1.sup.i=p,j=p f(AA[h.sub.i-1 +1 . . . h.sub.i,.nu..sub.j-1 +1 . . . .nu..sub.j])
Given a desired number of partitions p, a practical example of a two dimensional p.times.p partition problem using an additive weight function is now given.
For data stored in two dimensional arrays, several high performance computing languages allow the user to specify a partitioning and distribution of data onto a logical set of processors. An example of such a scheme is what is known as the generalized block distribution in HPF (high performance Fortran), which is a two dimensional p.times.p partition problem using an additive weight function F.
The two dimensional p.times.p partition problem using a Hamming weight function is exhibited in motion-compensated video compression by block matching. Since successive frames of a video sequence are strongly correlated, frames can be compressed by reference to the preceding ones. This can be improved by first estimating portions of the current frame which correspond to moving objects and then transmitting motion vectors that indicate to the decoder where to look at the previous frame to predict the current one. The most popular method for estimating the motion vectors is called block matching as discussed in J. Jain and A. Jain, "Displacement Measurement and its Application in Interframe Coding", IEEE Transactions on Communications, vol. 29, pp. 1799-1808 (1981), which is expressly incorporated herein by reference. This involves tiling the current frame with blocks and estimating the motion vectors for each block individually. The motion vector for a given block is usually obtained by minimizing, from among candidates v within a limited search area, some norm of the difference between the block and the previous frame at v. An example is the minimum Hamming distance between B and v within a window of width C around the position corresponding to B in the previous frame, for some parameter C. The main variation is in how the current frame is tiled. Some extant tilings use fixed-sized blocks as discussed in J. Jain and A. Jain, "Displacement Measurement and its Application in Interframe Coding", IEEE Transactions on Communications, vol. 29, pp. 1799-1808 (1981), superblocks as discussed in B. Carpentieri and J. Storer, "A Split-Merge Parallel Block Matching Algorithm for Video Displacement Estimation", Proc. Of IEEE Data Compression Conference, pp. 239-248 (1992), and quadtrees as discussed in D. Hoang, P. Long and J. Vitter, "Explicit Bit Minimization For Motion-Compensated Video Coding", Proc. Data Compression Conference", (1995); G. Martin, R. Packwood and I. Rhee, "Variable Size Block Matching Motion Estimation With Minimal Error", Proc. IS & T/SPIE Symp. On Electronic Imaging: Science and Technology, (Jan. 1996); and I. Rhee, G. Martin, S. Muthukrishnan, and R. Packwood, "Variable Size Block Matching Motion Estimation Based on Quad Trees With Minimal Error", (submitted 1997), all of which are expressly incorporated herein by reference. Given the desire to determine a p.times.p partition as discussed herein, the problem then becomes one of computing the best tiling. This is precisely our two dimensional .delta.-weight partition problem using a Hamming weight function H.sub.c. Here, the desired weight .delta. is the error threshold set in accordance with the particular application.
See D. Hoang, P. Long and J. Vitter, "Explicit Bit Minimization For Motion-Compensated Video Coding", Proc. Data Compression Conference", (1995); and G. Martin, R. Packwood and I. Rhee, "Variable Size Block Matching Motion Estimation With Minimal Error", Proc. IS & T/SPIE Symp. On Electronic Imaging: Science and Technology, (Jan. 1996) and references therein, or "Block Matching Methods", http://www.ee.princeton.edu/santanu/journal/paper/node3.html, for background on block matching, all of which are expressly incorporated herein by reference.
Whereas a one dimensional array of data can typically be partitioned to an exact optimum solution in a reasonable amount of time, a two dimensional array must be partitioned to an approximation only, to be solved reasonably fast.
A number of methods are known for block matching, e.g., as requiring the solution of a two dimensional .delta.-weight problem using a Hamming weight function H.sub.c. These conventional methods essentially work by splitting subareas greedily until each subarea has a weight of at most the desired maximum weight .delta.. However, the conventional methods do not provide any guarantees as to the number of partitions (or blocks) required. As disclosed in M. Grigni and F. Manne, "On the Complexity of the Generalized Block Distribution", Proc. Of .sub.3 rd International Workshop on Parallel Algorithms for Irregularly Structured Problems, Lecture Notes in Computer Science 1117, Springer, pp. 319-326 (1996) (which is expressly incorporated herein by reference), the solution using the conventional methods is considered to be "NP-hard".
For the p.times.p partition problem using an additive weight function F, Grigni and Manne showed that the two dimensional p.times.p partition problem is NP-hard even when the given array consists of 0/1 entries. Independently, Charikar et. al have given a simple proof that this problem is APX-hard, that is, the problem is in fact NP-hard to approximate within a factor of two. While a number of natural heuristic algorithms are known for this problem (See for example Grigni and Manne), most of them can be shown to provide poor approximations, e.g., to only about .OMEGA.(p). The currently best known approximating technique provides a performance of only 0(p)(See M. Hallsorsson and F. Manne, "Manuscript" (1996)). Table II below summarizes the results of various conventional techniques.
REFERENCE RESULT Grigni & Manne NP-Hardness Charikar et al. APX-Hardness Halldorsson & Manne O(p) approximation
There is a need to improve the speed of an approximated solution for an array either given the desired maximum weight of any block or given the desired number of partitions, for a two and greater dimensional array, and/or to strike an improved balance between greater speed and increased accuracy.